package com.yanggu.scala.chapater05

object FunDemo02 {

  def main(args: Array[String]): Unit = {
    //1. 使用递归的方式求出菲波那切数列的值。给定一个整数n，打印对应的斐波那契额数
    println(f1(40))

    //2. 计算f(1) = 3; f(n) = 2 * f(n - 1) + 1;
    //计算当n = 10时, f(10)的值
    println(f(10))

    //3. 猴子吃桃问题
    //有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再多吃一个。
    //当到第十天时，想再吃时（还没吃），发现只有1个桃子了。问题：最初共多少个桃子？
    println(f2(10))
  }

  def f1(num: Int): Int = {
    if (num == 1 || num == 2) {
      1
    } else {
      f1(num - 1) + f1(num - 2)
    }
  }

  def f(num: Int): Int = {
    if (num == 1) {
      3
    } else {
      2 * f(num - 1) + 1
    }
  }

  /**
   * 递归的思想。
   * 方法或者是函数自己调用自己本身，就是递归。
   * 编写递归程序的原则
   * 1. 一定要有递归的出口。
   * 2. 将一个大的问题转换成更小的问题。直到最基本的问题
   *
   * @param num
   * @return
   */
  def f2(num: Int): Int = {
    if (num == 1) {
      1
    } else {
      (f2(num - 1) + 1) * 2
    }
  }

}
